/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘柄华
 * Date: 2022-05-22
 * Time: 15:38
 */
public class TestDemo01 {
    /*
    * 年终奖问题 给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
    *动态规划:  当前点的最大总价值 = max(上面点最大总价值，左边点的最大总价值) + 当前点价值
    *          (0, 0)点以及第一行和第一列要先初始化一波
    * */
    public int getMost(int[][] board) {
        int n = board.length;
        int[][] dp = new int[n][n];
        dp[0][0] = board[0][0];
        for(int i=1;i<n;i++){
            dp[i][0] = dp[i-1][0]+board[i][0];
        }
        for(int i=1;i<n;i++){
            dp[0][i] = dp[0][i-1]+board[0][i];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = board[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[n-1][n-1];
    }
}
